{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Change Minimum Characters to Satisfy One of Three Conditions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #counting #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #计数 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCharacters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #满足三条件之一需改变的最少字符数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串 <code>a</code> 和 <code>b</code> ，二者均由小写字母组成。一步操作中，你可以将 <code>a</code> 或 <code>b</code> 中的 <strong>任一字符</strong> 改变为 <strong>任一小写字母</strong> 。</p>\n",
    "\n",
    "<p>操作的最终目标是满足下列三个条件 <strong>之一</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>a</code> 中的 <strong>每个字母</strong> 在字母表中 <strong>严格小于</strong> <code>b</code> 中的 <strong>每个字母</strong> 。</li>\n",
    "\t<li><code>b</code> 中的 <strong>每个字母</strong> 在字母表中 <strong>严格小于</strong> <code>a</code> 中的 <strong>每个字母</strong> 。</li>\n",
    "\t<li><code>a</code> 和 <code>b</code> <strong>都</strong> 由 <strong>同一个</strong> 字母组成。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回达成目标所需的 <strong>最少</strong> 操作数<em>。</em></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = \"aba\", b = \"caa\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>满足每个条件的最佳方案分别是：\n",
    "1) 将 b 变为 \"ccc\"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；\n",
    "2) 将 a 变为 \"bbb\" 并将 b 变为 \"aaa\"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；\n",
    "3) 将 a 变为 \"aaa\" 并将 b 变为 \"aaa\"，2 次操作，满足 a 和 b 由同一个字母组成。\n",
    "最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = \"dabadd\", b = \"cda\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>满足条件 1 的最佳方案是将 b 变为 \"eee\" 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= a.length, b.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>a</code> 和 <code>b</code> 只由小写字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [change-minimum-characters-to-satisfy-one-of-three-conditions](https://leetcode.cn/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [change-minimum-characters-to-satisfy-one-of-three-conditions](https://leetcode.cn/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aba\"\\n\"caa\"', '\"dabadd\"\\n\"cda\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        n1, n2 = len(a), len(b)\n",
    "        ca, cb = defaultdict(int), defaultdict(int)\n",
    "\n",
    "        for x in a:\n",
    "            ca[ord(x) - 97] += 1\n",
    "        for y in b:\n",
    "            cb[ord(y) - 97] += 1\n",
    "\n",
    "        \n",
    "        ans = n1 - max(ca.values()) + n2 - max(cb.values())\n",
    "        # condition 1 (a < b)\n",
    "        for x in range(25):\n",
    "            ca[x + 1] += ca[x]\n",
    "            cb[x + 1] += cb[x]\n",
    "            ans = min(ans, n1 - ca[x] + cb[x])\n",
    "            ans = min(ans, n2 - cb[x] + ca[x])\n",
    "        \n",
    "        \n",
    "             \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        m, n = len(a), len(b)\n",
    "        smalla = [0] * 26\n",
    "        smallb = [0] * 26\n",
    "        ca = Counter(a)\n",
    "        cb = Counter(b)\n",
    "        for i, c in enumerate(ascii_lowercase):\n",
    "            smalla[i] = ca[c]\n",
    "            smallb[i] = cb[c]\n",
    "        pre_sm_a = list(accumulate(smalla, initial=0))\n",
    "        pre_sm_b = list(accumulate(smallb, initial=0))\n",
    "        ans = inf\n",
    "        for i in range(26):\n",
    "            if i != 0:\n",
    "                ans = min(ans, m-pre_sm_a[i]+pre_sm_b[i])\n",
    "                ans = min(ans, n-pre_sm_b[i]+pre_sm_a[i])\n",
    "            ans = min(ans, m+n-smalla[i]-smallb[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        mina, maxa = min(a), max(a)\n",
    "        minb, maxb = min(b), max(b)\n",
    "        if maxa < minb:\n",
    "            return 0\n",
    "        if maxb < mina:\n",
    "            return 0\n",
    "        if mina == maxa == minb == maxb:\n",
    "            return 0\n",
    "        cnta = [0] * 26\n",
    "        for x in a:\n",
    "            cnta[ord(x) - ord('a')] += 1\n",
    "        cntb = [0] * 26\n",
    "        for x in b:\n",
    "            cntb[ord(x) - ord('a')] += 1\n",
    "        ret = 10 ** 5\n",
    "        def go(a, b, cnta, cntb):\n",
    "            nonlocal ret\n",
    "            for i in range(25):\n",
    "                cnt = 0\n",
    "                for j in range(i + 1, 26):\n",
    "                    cnt += cnta[j]\n",
    "      \n",
    "                for j in range(i + 1):\n",
    "                    cnt += cntb[j]\n",
    "                \n",
    "                \n",
    "                ret = min(ret, cnt)\n",
    "        go(a, b, cnta, cntb)\n",
    "        go(b, a, cntb, cnta)\n",
    "        for i in range(26):\n",
    "            ret = min(ret, len(a) - cnta[i] + len(b) - cntb[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        cnta, cntb = Counter(a), Counter(b)\n",
    "        n, m = len(a), len(b)\n",
    "        ret = n + m - cnta['a'] - cntb['a']\n",
    "        preSuma, preSumb = 0, 0\n",
    "        for ch in range(ord('z'), ord('a'), -1):\n",
    "            ret = min(ret, n + m - cnta[chr(ch)] - cntb[chr(ch)])\n",
    "            ret = min(ret, n - preSuma - cnta[chr(ch)] + preSumb + cntb[chr(ch)])\n",
    "            ret = min(ret, m - preSumb - cntb[chr(ch)] + preSuma + cnta[chr(ch)])\n",
    "            preSuma += cnta[chr(ch)]\n",
    "            preSumb += cntb[chr(ch)]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        count_a, count_b = [0]*26, [0]*26\n",
    "        for ch in a:\n",
    "            count_a[ord(ch)-ord('a')] += 1\n",
    "        for ch in b:\n",
    "            count_b[ord(ch)-ord('a')] += 1\n",
    "        presum_a, presum_b = list(accumulate(count_a, initial=0)), list(accumulate(count_b, initial=0))\n",
    "        option1 = min(presum_a[-1]-presum_a[i]+presum_b[i] for i in range(1, 26))\n",
    "        option2 = min(presum_a[i]+presum_b[-1]-presum_b[i] for i in range(1, 26))\n",
    "        option3 = min(len(a)-count_a[i]+len(b)-count_b[i] for i in range(26))\n",
    "        return min(option1, option2, option3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        counter_a, counter_b = [0] * 26, [0] * 26\n",
    "        for c in a:\n",
    "            counter_a[ord(c) - ord('a')] += 1\n",
    "        for c in b:\n",
    "            counter_b[ord(c) - ord('a')] += 1\n",
    "        length = len(a + b)\n",
    "        way1 = min(sum(counter_a[i:]) + sum(counter_b[:i]) for i in range(1,26))\n",
    "        way2 = min(sum(counter_b[i:]) + sum(counter_a[:i]) for i in range(1,26))\n",
    "        way3 = min(length - counter_a[i] - counter_b[i] for i in range(26))\n",
    "        return min(way1, way2, way3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        na = len(a)\n",
    "        nb = len(b)\n",
    "        mapping_a = [0]*26\n",
    "        mapping_b = [0]*26 \n",
    "        for c in a:\n",
    "            mapping_a[ord(c)-ord('a')] += 1\n",
    "        for c in b:\n",
    "            mapping_b[ord(c)-ord('a')] += 1\n",
    "        result = float('inf')\n",
    "        prea = 0\n",
    "        preb = 0\n",
    "        for i in range(25):\n",
    "            prea += mapping_a[i]\n",
    "            preb += mapping_b[i]\n",
    "            # a < b\n",
    "            result = min(result, prea + nb - preb)\n",
    "            # b < a\n",
    "            result = min(result, preb + na - prea)\n",
    "            # a == b \n",
    "            result = min(result, na - mapping_a[i] + nb - mapping_b[i])\n",
    "        result = min(result, na - mapping_a[25] + nb - mapping_b[25])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        na = len(a)\n",
    "        nb = len(b)\n",
    "        mapping_a = [0]*26\n",
    "        mapping_b = [0]*26 \n",
    "        for c in a:\n",
    "            mapping_a[ord(c)-ord('a')] += 1\n",
    "        for c in b:\n",
    "            mapping_b[ord(c)-ord('a')] += 1\n",
    "        result = float('inf')\n",
    "        prea = 0\n",
    "        preb = 0\n",
    "        for i in range(25):\n",
    "            prea += mapping_a[i]\n",
    "            preb += mapping_b[i]\n",
    "            # a < b\n",
    "            result = min(result, prea + nb - preb)\n",
    "            # b < a\n",
    "            result = min(result, preb + na - prea)\n",
    "            # a == b \n",
    "            result = min(result, na - mapping_a[i] + nb - mapping_b[i])\n",
    "        result = min(result, na - mapping_a[25] + nb - mapping_b[25])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        m = [0 for _ in range(26)]\n",
    "        n = [0 for _ in range(26)]\n",
    "        for c in a:\n",
    "            m[ord(c) - ord('a')] += 1\n",
    "        for c in b:\n",
    "            n[ord(c) - ord('a')] += 1\n",
    "        la = len(a)\n",
    "        lb = len(b)\n",
    "        ans = sys.maxsize\n",
    "        cnta = 0\n",
    "        cntb = 0\n",
    "        for i in range(25):\n",
    "            cnta += m[i]\n",
    "            cntb += n[i]\n",
    "            ans = min(ans, la+lb-m[i]-n[i], la-cnta+cntb, lb-cntb+cnta)\n",
    "        return min(ans, la+lb-m[25]-n[25])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        A = [0] * 26 \n",
    "        B = [0] * 26\n",
    "        # for c1, c2 in zip(a,b):\n",
    "        #     A[ord(c1) - ord('a')] +=1\n",
    "        #     B[ord(c1) - ord('a')] +=1\n",
    "        for ch in a:    \n",
    "            A[ord(ch)-ord('a')] += 1\n",
    "        for ch in b:    \n",
    "            B[ord(ch)-ord('a')] += 1\n",
    "\n",
    "        n1 , n2 = len(a),len(b)\n",
    "        p1 = p2 = 0\n",
    "        ans = n1 + n2\n",
    "\n",
    "        for i in range(25):\n",
    "            p1 += A[i]\n",
    "            p2 += B[i]\n",
    "            ans = min(ans, n1 - p1 + p2 , p1 + n2 - p2, n1 - A[i] + n2 - B[i])\n",
    "        \n",
    "        ans = min(ans, n1-A[25] + n2-B[25])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        na = len(a)\n",
    "        nb = len(b)\n",
    "        mapping_a = [0]*26\n",
    "        mapping_b = [0]*26 \n",
    "        for c in a:\n",
    "            mapping_a[ord(c)-ord('a')] += 1\n",
    "        for c in b:\n",
    "            mapping_b[ord(c)-ord('a')] += 1\n",
    "        result = float('inf')\n",
    "        prea = 0\n",
    "        preb = 0\n",
    "        for i in range(25):\n",
    "            prea += mapping_a[i]\n",
    "            preb += mapping_b[i]\n",
    "            # a < b\n",
    "            result = min(result, prea + nb - preb)\n",
    "            # b < a\n",
    "            result = min(result, preb + na - prea)\n",
    "            # a == b \n",
    "            result = min(result, na - mapping_a[i] + nb - mapping_b[i])\n",
    "        result = min(result, na - mapping_a[25] + nb - mapping_b[25])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        acnt, bcnt = [0]*26, [0]*26\n",
    "        an, bn = len(a), len(b)\n",
    "\n",
    "        for c in a:\n",
    "            acnt[ord(c)-ord('a')]+=1\n",
    "        for c in b:\n",
    "            bcnt[ord(c)-ord('a')]+=1\n",
    "\n",
    "        ans, asum, bsum = sys.maxsize, 0, 0\n",
    "\n",
    "        for i in range(25):\n",
    "            asum+=acnt[i]\n",
    "            bsum+=bcnt[i]\n",
    "            ans = min(min(ans, an-acnt[i]+bn-bcnt[i]), min(an-asum+bsum, bn-bsum+asum))\n",
    "        \n",
    "        ans = min(ans, an-acnt[25]+bn-bcnt[25])\n",
    "    \n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        cnts = collections.Counter(a + b)\n",
    "        \n",
    "        p3_res = len(a) + len(b) - max(cnts.values())\n",
    "\n",
    "\n",
    "\n",
    "        cntA = [0] * 26\n",
    "        cntB = [0] * 26\n",
    "\n",
    "        for ss in a:\n",
    "            cntA[ord(ss) - 97] += 1\n",
    "        \n",
    "        for ss in b:\n",
    "            cntB[ord(ss) - 97] += 1\n",
    "\n",
    "        a_left = cntA[0]\n",
    "        a_right = len(a) - a_left\n",
    "        \n",
    "        b_left = cntB[0]\n",
    "        b_right = len(b) - b_left\n",
    "\n",
    "        res = min(a_right + b_left, a_left + b_right)\n",
    "\n",
    "\n",
    "        i = 1\n",
    "        while i < 25:\n",
    "            a_left += cntA[i]\n",
    "            a_right -= cntA[i]\n",
    "\n",
    "            b_left += cntB[i]\n",
    "            b_right -= cntB[i]\n",
    "\n",
    "            res = min(res, a_right + b_left, a_left + b_right)\n",
    "            i += 1\n",
    "\n",
    "        return min(res, p3_res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCharacters(self, a: str, b: str) -> int:\r\n",
    "        #\r\n",
    "        def less(s: str, ch: str) -> int:\r\n",
    "            ress = 0 \r\n",
    "            for c in s:\r\n",
    "                if c > ch:\r\n",
    "                    ress += 1\r\n",
    "            return ress \r\n",
    "             \r\n",
    "        def more(s: str, ch: str) -> int:\r\n",
    "            if ch =='z':\r\n",
    "                return inf\r\n",
    "            ress = 0 \r\n",
    "            for c in s:\r\n",
    "                if c <= ch:\r\n",
    "                    ress += 1\r\n",
    "            return ress\r\n",
    "        \r\n",
    "        cnt = Counter(a + b) \r\n",
    "        res = len(a) + len(b) - max(cnt.values())\r\n",
    "        for ch in ascii_lowercase:\r\n",
    "            res = min(res, less(a, ch) + more(b, ch), less(b, ch) + more(a, ch))\r\n",
    "            if ch == 'c':\r\n",
    "                print(res, less(a, ch), more(b, ch), less(b, ch),more(a, ch)) \r\n",
    "        return res \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        an, bn = len(a), len(b)\n",
    "        acnt, bcnt = [0]*26, [0]*26\n",
    "        aord = ord('a')\n",
    "\n",
    "        for c in a:\n",
    "            acnt[ord(c)-aord] += 1\n",
    "\n",
    "        for c in b:\n",
    "            bcnt[ord(c)-aord] += 1\n",
    "\n",
    "        asm = bsm = 0\n",
    "        ans = an + bn\n",
    "\n",
    "        for i in range(25):\n",
    "            if acnt[i] == bcnt[i] == 0:\n",
    "                continue \n",
    "            asm += acnt[i]\n",
    "            bsm += bcnt[i]\n",
    "            ans = min(ans, asm+bn-bsm, bsm+an-asm, an+bn-acnt[i]-bcnt[i])\n",
    "\n",
    "        ans = min(ans, an+bn-acnt[25]-bcnt[25])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        ansa = [0] * 26\n",
    "        ansb = [0] * 26\n",
    "        lena = len(a)\n",
    "        lenb = len(b)\n",
    "        res = inf\n",
    "        for i in a: ansa[ord(i) - ord('a')] += 1\n",
    "        for i in b: ansb[ord(i) - ord('a')] += 1\n",
    "        suma = sumb = 0\n",
    "        for i in range(26):\n",
    "            suma += ansa[i]\n",
    "            sumb += ansb[i]\n",
    "            if i < 25:\n",
    "                res = min(res, lena + lenb - ansa[i] - ansb[i], lena - suma + sumb, lenb - sumb + suma)\n",
    "            else:\n",
    "                res = min(res, lena + lenb - ansa[i] - ansb[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        counter1,counter2=[0]*26,[0]*26\n",
    "        for c in a: counter1[ord(c)-ord('a')]+=1\n",
    "        for c in b: counter2[ord(c)-ord('a')]+=1\n",
    "        way1=way2=way3=1000000\n",
    "        for i in range(26):\n",
    "            if i>0:\n",
    "                way1=min(way1,sum(counter1[i:])+sum(counter2[:i]))\n",
    "                way2=min(way2,sum(counter2[i:])+sum(counter1[:i]))\n",
    "            way3=min(way3,len(a)+len(b)-counter1[i]-counter2[i])\n",
    "        return min(way1,way2,way3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        m, n = len(a), len(b)\n",
    "        \n",
    "        # 计算每个字符串中每个字符的频率\n",
    "        count_a, count_b = [0] * 26, [0] * 26\n",
    "        for char in a:\n",
    "            count_a[ord(char) - ord('a')] += 1\n",
    "        for char in b:\n",
    "            count_b[ord(char) - ord('a')] += 1\n",
    "            \n",
    "        # 计算情况3的代价\n",
    "        ans = m + n - max((count_a[i] + count_b[i] for i in range(26)))\n",
    "        \n",
    "        # 计算情况1和情况2的代价\n",
    "        for i in range(25):  # 最多只需要考虑到y，因为z之后没有字符\n",
    "            # 使用前缀和\n",
    "            if i > 0:\n",
    "                count_a[i] += count_a[i-1]\n",
    "                count_b[i] += count_b[i-1]\n",
    "            # a中的每个字符小于b中的每个字符\n",
    "            cost1 = count_b[i] + (m - count_a[i])\n",
    "            # b中的每个字符小于a中的每个字符\n",
    "            cost2 = count_a[i] + (n - count_b[i])\n",
    "            ans = min(ans, cost1, cost2)\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        counter1,counter2=[0]*26,[0]*26\n",
    "        for char in a: counter1[ord(char)-ord('a')]+=1\n",
    "        for char in b: counter2[ord(char)-ord('a')]+=1\n",
    "        way1=min(\n",
    "            (sum(counter1[i:])+sum(counter2[:i])) for i in range(1,26)\n",
    "        )\n",
    "        way2=min(\n",
    "            (sum(counter2[i:])+sum(counter1[:i])) for i in range(1,26)\n",
    "        )\n",
    "        way3=min(\n",
    "            len(a)+len(b)- counter1[i]-counter2[i] for i in range(26)\n",
    "        )\n",
    "        return min(way1,way2,way3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        # count_a, count_b = [0]*26, [0]*26\n",
    "        # for ch in a:\n",
    "        #     count_a[ord(ch)-ord('a')] += 1\n",
    "        # for ch in b:\n",
    "        #     count_b[ord(ch)-ord('a')] += 1\n",
    "        # presum_a, presum_b = list(accumulate(count_a, initial=0)), list(accumulate(count_b, initial=0))\n",
    "        # option1 = min(presum_a[-1]-presum_a[i]+presum_b[i] for i in range(1, 26))\n",
    "        # option2 = min(presum_a[i]+presum_b[-1]-presum_b[i] for i in range(1, 26))\n",
    "        # option3 = min(len(a)-count_a[i]+len(b)-count_b[i] for i in range(26))\n",
    "        # return min(option1, option2, option3)\n",
    "\n",
    "        # -------------------------------\n",
    "        # '''\n",
    "        # 方案3是个定值只需记录一下比较即可\n",
    "        # 方案1和方案2思想等价\n",
    "        # 从26个小写字母依次遍历，作为一条基准线，基准线左边的都比它小，右边的都比它大，\n",
    "        # 满足条件1：可以分别取a左边和b右边，剩下的a右边和b左边个数作为候选答案\n",
    "        # 或者满足条件2：取b左边和a右边，剩下的b右边和a左边个数作为候选答案，比较取最小值即可\n",
    "        # '''   \n",
    "        # a = [ord(i)-97 for i in a]\n",
    "        # b = [ord(i)-97 for i in b]       \n",
    "        # AA = Counter(a)\n",
    "        # BB = Counter(b)\n",
    "        # C =AA+BB\n",
    "        # ans = sum(C.values())-max(C.values())\n",
    "        # A = [0]*26\n",
    "        # B = [0]*26\n",
    "        # for k,v in AA.items():\n",
    "        #     A[k] = v\n",
    "        # for k,v in BB.items():\n",
    "        #     B[k] = v\n",
    "        # for i in range(1,26):#确定基线\n",
    "        #     ans = min(ans,sum(A[i:])+sum(B[:i]))\n",
    "        #     ans = min(ans,sum(B[i:])+sum(A[:i]))          \n",
    "        # return ans\n",
    "\n",
    "        # -----------------------------------\n",
    "        counter_a =[a.count(chr(97+i)) for i in range(26)]\n",
    "        counter_b =[b.count(chr(97+i)) for i in range(26)]\n",
    "        \n",
    "        #rule_three\n",
    "        result = len(a)+len(b) - max(counter_a[i]+counter_b[i] for i in range(26))\n",
    "\n",
    "        #rule_one and two\n",
    "        rule_one=len(a)\n",
    "        rule_two=len(b)\n",
    "        for i in range(25):\n",
    "            rule_one += counter_b[i]-counter_a[i]\n",
    "            rule_two += counter_a[i]-counter_b[i]\n",
    "            result = min(result,rule_one,rule_two)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        cnt1 = [0] * 26\n",
    "        cnt2 = [0] * 26\n",
    "        for x in a:\n",
    "            x = ord(x) - ord('a')\n",
    "            cnt1[x] += 1\n",
    "        for y in b:\n",
    "            y = ord(y) - ord('a')\n",
    "            cnt2[y] += 1\n",
    "        pre_sum1 = list(accumulate(cnt1, initial = 0))\n",
    "        pre_sum2 = list(accumulate(cnt2, initial = 0))\n",
    "\n",
    "        na, nb = len(a), len(b)\n",
    "        ans = inf\n",
    "        for i in range(25):\n",
    "            res1 = pre_sum1[i + 1] - pre_sum1[0] + pre_sum2[-1] - pre_sum2[i + 1]\n",
    "            res2 = pre_sum2[i + 1] - pre_sum2[0] + pre_sum1[-1] - pre_sum1[i + 1]\n",
    "            res3 = na + nb - (cnt1[i] + cnt2[i])\n",
    "            ans = min(ans, res1, res2, res3)\n",
    "        res1 = cnt1[-1] + pre_sum2[-2]\n",
    "        res2 = cnt2[-1] + pre_sum1[-2]\n",
    "        res3 = na + nb - (cnt1[-1] + cnt2[-1])\n",
    "        ans = min(ans, res1, res2, res3)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        da = {}\n",
    "        db = {}\n",
    "        for i in range(26):\n",
    "            key = chr(ord('a') + i)\n",
    "            da[key] = a.count(key)\n",
    "            db[key] = b.count(key)\n",
    "        result = float('inf')\n",
    "        r1 = self.op1(da, db)\n",
    "        result = min(r1, result)\n",
    "        r2 = self.op1(db, da)\n",
    "        result = min(r2, result)\n",
    "        r3 = self.op2(da, db)\n",
    "        result = min(len(a)+len(b)-r3, result)\n",
    "        return result\n",
    "\n",
    "\n",
    "    def op1(self, a, b):\n",
    "        result = float('inf')\n",
    "        for i in range(1, 26):\n",
    "            c = 0\n",
    "            bound = chr(ord('a') + i) \n",
    "            for key in a:\n",
    "                if key >= bound:\n",
    "                    c += a[key]\n",
    "            for key in b:\n",
    "                if key < bound:\n",
    "                    c += b[key]\n",
    "            result = min(result, c)\n",
    "        return result\n",
    "    \n",
    "    def op2(self, a, b):\n",
    "        new_dict = {}\n",
    "        for key in a:\n",
    "            new_dict[key] = a[key]\n",
    "        for key in b:\n",
    "            new_dict[key] = new_dict.get(key) + b[key]\n",
    "        new_dict = sorted(new_dict.items(), key=lambda x:x[1], reverse=True)\n",
    "        return new_dict[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        ca = collections.Counter(a)\n",
    "        cb = collections.Counter(b)\n",
    "        cc = ca + cb\n",
    "        res = len(a) + len(b) - max(cc.values())\n",
    "        nord = lambda x: ord(x)-97\n",
    "        for bd in range(nord('a'),nord('z')):\n",
    "            # res1代表将a改为严格小于b中字母的最少操作数\n",
    "            # res2代表将b改为严格小于a中字母的最少操作数\n",
    "            res1,res2 = 0,0 \n",
    "            for c in ca:\n",
    "                # 若c大于boundary则需要\n",
    "                if nord(c) > bd: \n",
    "                    res1 += ca[c]\n",
    "                else:\n",
    "                    res2 += ca[c] \n",
    "            for c in cb:\n",
    "                if nord(c) > bd:\n",
    "                    res2 += cb[c]\n",
    "                else:\n",
    "                    res1 += cb[c]\n",
    "            res = min(res,res1,res2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        cnta = Counter(a)\n",
    "        cntb = Counter(b)\n",
    "        na = len(a)\n",
    "        nb = len(b)\n",
    "        ma = max(cnta.values())\n",
    "        mb = max(cntb.values())\n",
    "        ans = na - ma + nb - mb\n",
    "        # 计算使得cnt1所有字符都>cnt2所有字符的最少操作次数\n",
    "        def cal(cnt1, cnt2) -> int:\n",
    "            res = inf\n",
    "            # 枚举cnt1最小的字符是c\n",
    "            for c in 'bcdefghijklmnopqrstuvwxyz':\n",
    "                t = sum(cnt1[c1] for c1 in cnt1 if c1 < c) + sum(cnt2[c2] for c2 in cnt2 if c2 >= c)\n",
    "                res = min(res, t)\n",
    "            return res\n",
    "        ans = min(ans, cal(cnta, cntb))\n",
    "        ans = min(ans, cal(cntb, cnta))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        na = len(a)\n",
    "        nb = len(b)\n",
    "        mapping_a = [0]*26\n",
    "        mapping_b = [0]*26 \n",
    "        for c in a:\n",
    "            mapping_a[ord(c)-ord('a')] += 1\n",
    "        for c in b:\n",
    "            mapping_b[ord(c)-ord('a')] += 1\n",
    "        result = float('inf')\n",
    "        prea = 0\n",
    "        preb = 0\n",
    "        for i in range(25):\n",
    "            prea += mapping_a[i]\n",
    "            preb += mapping_b[i]\n",
    "            # a < b\n",
    "            result = min(result, prea + nb - preb)\n",
    "            # b < a\n",
    "            result = min(result, preb + na - prea)\n",
    "            # a == b \n",
    "            result = min(result, na - mapping_a[i] + nb - mapping_b[i])\n",
    "        result = min(result, na - mapping_a[25] + nb - mapping_b[25])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        va = [0] * 26\n",
    "        vb = [0] * 26\n",
    "        for c in a:\n",
    "            va[ord(c) - ord('a')] += 1\n",
    "        for c in b:\n",
    "            vb[ord(c) - ord('a')] += 1\n",
    "        \n",
    "        t = 0\n",
    "        for i in range(26):\n",
    "            t = max(t, va[i] + vb[i])\n",
    "        \n",
    "        sa = len(a)\n",
    "        sb = len(b)\n",
    "        res = sa + sb - t\n",
    "        for i in range(25, 0, -1):\n",
    "            ta = sum(va[i:])\n",
    "            tb = sum(vb[i:])\n",
    "            res = min(res, min(ta + sb - tb, tb + sa - ta))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        counter1,counter2=[0]*26,[0]*26\n",
    "        for c in a: counter1[ord(c)-ord('a')]+=1\n",
    "        for c in b: counter2[ord(c)-ord('a')]+=1\n",
    "        way1=min(sum(counter1[i:])+sum(counter2[:i]) for i in range(1,26))\n",
    "        way2=min(sum(counter2[i:])+sum(counter1[:i]) for i in range(1,26))\n",
    "        way3=min(len(a)+len(b)-counter1[i]-counter2[i] for i in range(26))\n",
    "        return min(way1,way2,way3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        count_a, count_b = [0]*26, [0]*26\n",
    "        for i in range(len(a)):\n",
    "            count_a[ord(a[i])-97] += 1\n",
    "        for i in range(len(b)):\n",
    "            count_b[ord(b[i])-97] += 1\n",
    "        res = float('inf')\n",
    "        for i in range(1, 26):\n",
    "            temp = sum(count_a[:i]) + sum(count_b[i:])\n",
    "            res = min(res, temp)\n",
    "        for i in range(25):\n",
    "            temp = sum(count_a[i+1:]) + sum(count_b[:i+1])\n",
    "            res = min(res, temp)\n",
    "        same_char = max(count_a[i] + count_b[i] for i in range(26))\n",
    "        res = min(res, len(a)+len(b)-same_char)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        counter1,counter2=[0]*26,[0]*26\n",
    "        for c in a: counter1[ord(c)-ord('a')]+=1\n",
    "        for c in b: counter2[ord(c)-ord('a')]+=1\n",
    "        way1=min(sum(counter1[i:])+sum(counter2[:i]) for i in range(1,26))\n",
    "        way2=min(sum(counter2[i:])+sum(counter1[:i]) for i in range(1,26))\n",
    "        way3=min(len(a)+len(b)-counter1[i]-counter2[i] for i in range(26))\n",
    "        return min(way1,way2,way3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        cnt1 = [0] * 26\n",
    "        cnt2 = [0] * 26\n",
    "        for x in a:\n",
    "            x = ord(x) - ord('a')\n",
    "            cnt1[x] += 1\n",
    "        for y in b:\n",
    "            y = ord(y) - ord('a')\n",
    "            cnt2[y] += 1\n",
    "        pre_sum1 = list(accumulate(cnt1, initial = 0))\n",
    "        pre_sum2 = list(accumulate(cnt2, initial = 0))\n",
    "\n",
    "        na, nb = len(a), len(b)\n",
    "        ans = inf\n",
    "        #print(cnt1, cnt2)\n",
    "        #p##rint(pre_sum1, pre_sum2)\n",
    "        for i in range(25):\n",
    "            res1 = pre_sum1[i + 1] - pre_sum1[0] + pre_sum2[-1] - pre_sum2[i + 1]\n",
    "            #print(i, pre_sum2[i + 1] - pre_sum2[0], pre_sum1[-1] - pre_sum1[i + 1])\n",
    "            res2 = pre_sum2[i + 1] - pre_sum2[0] + pre_sum1[-1] - pre_sum1[i + 1]\n",
    "            res3 = na + nb - (cnt1[i] + cnt2[i])\n",
    "            #print(i, ans, res1, res2, res3)\n",
    "            ans = min(ans, res1, res2, res3)\n",
    "        res1 = cnt1[-1] + pre_sum2[-2]\n",
    "        res2 = cnt2[-1] + pre_sum1[-2]\n",
    "        res3 = na + nb - (cnt1[-1] + cnt2[-1])\n",
    "        ans = min(ans, res1, res2, res3)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def minCharacters(self, a: str, b: str) -> int:\n",
    "        ta,tb = [0] * 26, [0] * 26\n",
    "        na,nb = len(a),len(b)\n",
    "        for c in a:\n",
    "            ta[ord(c)-97] += 1\n",
    "        for c in b:\n",
    "            tb[ord(c)-97] += 1\n",
    "        ans = na + nb\n",
    "        s1,s2 = 0,0\n",
    "        for i in range(25):\n",
    "            s1 += ta[i]\n",
    "            s2 += tb[i]\n",
    "            ans = min(ans, s1 + nb - s2, s2 + na - s1, na + nb - ta[i]-tb[i])\n",
    "        ans = min(ans,na+nb-ta[-1]-tb[-1])\n",
    "        return ans\n",
    "s =Solution()\n",
    "s.minCharacters(\"dabadd\",\"cda\")"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
